class Solution(object):
    def minimumScore(self, s, t):
        n = len(s)
        m = len(t)
        DP = [[-1 for _ in range(26)] for _ in range(n + 1)]
        for i in range(n - 2, -1, -1):
            c_ord = ord(s[i + 1]) - ord('a')
            for j in range(26):
                if j == c_ord:
                    DP[i + 1][j] = i + 2
                else:
                    DP[i + 1][j] = DP[i + 2][j]
        c_ord = ord(s[0]) - ord('a')
        for j in range(26):
            if j == c_ord:
                DP[0][j] = 1
            else:
                DP[0][j] = DP[1][j]
        prefix = [-1] * m
        last_index = 0
        for k in range(m):
            ord_c = ord(t[k]) - ord('a')
            next_index = DP[last_index][ord_c]
            if next_index == -1:
                break
            else:
                prefix[k] = next_index - 1
                last_index = next_index
        s = s[::-1]
        t = t[::-1]
        DP = [[-1 for _ in range(26)] for _ in range(n + 1)]
        for i in range(n - 2, -1, -1):
            c_ord = ord(s[i + 1]) - ord('a')
            for j in range(26):
                if j == c_ord:
                    DP[i + 1][j] = i + 2
                else:
                    DP[i + 1][j] = DP[i + 2][j]
        c_ord = ord(s[0]) - ord('a')
        for j in range(26):
            if j == c_ord:
                DP[0][j] = 1
            else:
                DP[0][j] = DP[1][j]
        suff = [-1] * m
        last_index = 0
        for k in range(m):
            ord_c = ord(t[k]) - ord('a')
            next_index = DP[last_index][ord_c]
            if next_index == -1:
                break
            else:
                suff[k] = n - next_index
                last_index = next_index
        suff = suff[::-1]
        left = 0
        right = 1
        min_val = m
        while left < m and prefix[left] >= 0:
            while right < m and prefix[left] >= suff[right]:
                right += 1
            if right == m:
                break
            else:
                min_val = min(min_val, right - left - 1)
                left += 1
                right = max(right, left + 1)
        while left < m and prefix[left] >= 0:
            left += 1
        right = 0
        while right < m and suff[right] == -1:
            right += 1
        return min(min_val, m - left, right)


data = Solution()
# s = "abacaba"
# t = "bzaa"
# print(data.minimumScore(s, t))
# s = "adebddaccdcabaade"
# t = "adbae"
# print(data.minimumScore(s, t))
s = "eeecaeecdeeadcdbcaa"
t = "edecabe"
print(data.minimumScore(s, t))